#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    const int mod = 1000000007;
    int threeSumMulti(vector<int>& arr, int target) {
        int n = arr.size();
        sort(arr.begin(), arr.end());
        int res = 0;
        for (int i = 0; i < n - 2; i++)
        {
            if (arr[i] + arr[i + 1] + arr[i + 2] > target) return res;
            if (arr[i] + arr[n - 1] + arr[n - 2] < target) continue;
            int left = i + 1, right = n - 1;
            while (left < right)
            {
                int sum = arr[i] + arr[left] + arr[right];
                if (sum < target) left++;
                else if (sum > target) right--;
                else if (arr[left] == arr[right])
                {
                    int diff = right - left + 1;
                    res = (res + diff * (diff - 1) / 2) % mod;
                    break;
                }
                else
                {
                    int l_cnt = 1, r_cnt = 1;
                    while (arr[left + 1] == arr[left++]) l_cnt++;
                    while (arr[right - 1] == arr[right--]) r_cnt++;
                    res = (res + l_cnt * r_cnt) % mod;
                }
            }
        }
        return res;
    }
};
int main()
{
	return 0;
}